package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/4/23 8:42
 */
public class C368 {

    LinkedList<Integer> ans;

    // zz.升序, 动态规划 , 我还以为有什么更优的解呢
    // 暴力解
    public List<Integer> largestDivisibleSubset(int[] nums) {
        ans = new LinkedList<>();
        if (nums.length == 1) {
            ans.add(nums[0]);
            return ans;
        }
        Arrays.sort(nums);
        List<Integer> res = new ArrayList<>();
        HashMap<Integer, HashMap<Integer, List<Integer>>> dp = new HashMap<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            List<Integer> p = process(nums, i, i, dp);
            res = res.size() > p.size() ? res : p;
        }
        return res;
    }

    public List<Integer> process(int[] nums, int pre, int cur, HashMap<Integer, HashMap<Integer, List<Integer>>> dp) {
        if (dp.containsKey(pre) && dp.get(pre).containsKey(cur)) {
            return dp.get(pre).get(cur);
        }
        List<Integer> res;
        if (cur < 0) {
            return new ArrayList<>(ans);
        } else {
            if (nums[pre] % nums[cur] == 0) {
                ans.addLast(nums[cur]);
                List<Integer> r1 = process(nums, cur, cur - 1, dp); // 要当前
                ans.removeLast();
                List<Integer> r2 = process(nums, pre, cur - 1, dp); // 不要当前
                res = r1.size() >= r2.size() ? r1 : r2;
            } else {    // 不能整除
                res = process(nums, pre, cur - 1, dp);
            }
        }
        if (!dp.containsKey(pre)) dp.put(pre, new HashMap<>());
        dp.get(pre).put(cur, res);
        return res;
    }

    // 返回最长的长度, 测试流程用的
    public int process2(int[] nums, int pre, int cur) {
        if (cur < 0) return 0;
        if (nums[pre] % nums[cur] == 0) {
            // p2 =      // 在可以整除的情况下要或不要当前, 倒序能整除就整除, 别做没用的尝试
            return Math.max(process2(nums, pre, cur - 1), process2(nums, cur, cur - 1) + 1);
        } else {    // 不能整除
            return process2(nums, pre, cur - 1);
        }
    }


    // for test
    public static void main(String[] args) {
        C368 test = new C368();


//        int[] nums = {1, 2, 3};
//        int[] nums = {1, 2, 3, 7, 8, 14, 21, 42, 84};
//        int[] nums = {4, 8, 10, 240};
//        int[] nums = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072,
//                262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456,
//                536870912, 1073741824};
        int[] nums = {1,2,4,8,9,72};
        System.out.println(test.largestDivisibleSubset(nums));

    }

}
